home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_09_02 / 9n02035a < prev    next >
Text File  |  1990-11-10  |  4KB  |  189 lines
  1.  
  2. Listing 2.
  3.  
  4. /* skiplist.c */
  5.  
  6. #define SLTEST  1
  7. #include <stdlib.h>
  8. #include <setjmp.h>
  9. #include "skiplist.h"
  10. #ifdef SLTEST
  11. #define NOMEM   1
  12. #endif
  13.  
  14. /*
  15.  *  Skip list routines based on algorithms described
  16.  *  by William Pugh, SKIP LISTS:  A PROBABILISTIC
  17.  *  ALTERNATIVE TO BALANCED TREES.  CACM, XXXIII, 6,
  18.  *  June, 1990.  Pp. 668 - 676.
  19.  */
  20.  
  21. NODE *newlist()
  22. {
  23.     NODE *temp;
  24.  
  25.     if(temp = (NODE *)calloc(sizeof(NODE) +
  26.         (sizeof(NODE *) * (DMAX - 1)), 1))
  27.     {
  28.         temp->korl.level = 1;
  29.     }
  30.     return(temp);
  31. }
  32.  
  33. NODE *search(searchlist, searchkey)
  34. NODE *searchlist;
  35. KEYTYPE searchkey;
  36. {
  37.     NODE *list, *temp;
  38.     int i, probe;
  39.  
  40.     list = searchlist;
  41.     for(i = searchlist->korl.level; --i >= 0; )
  42.     {
  43.         while(temp = list->pointers[i])
  44.         {
  45.             if((probe = COMPARE(temp->korl.key, searchkey))
  46.                 < 0)
  47.             {
  48.                 list = temp;
  49.             }
  50.             else if(probe == NIL)   /* key found */
  51.                 return(temp);
  52.             else
  53.                 break;
  54.         }
  55.     }
  56.     return(NIL);
  57. }
  58.  
  59. NODE *insert(searchlist, searchkey)
  60. NODE *searchlist;
  61. KEYTYPE searchkey;
  62. {
  63.     NODE *lnode, *tnode;
  64.     int i, newlevel, probe;
  65.     NODE *tempptrs[MAXLEVEL];
  66.  
  67.     lnode = searchlist;
  68.     for(i = searchlist->korl.level; --i >= 0; )
  69.     {
  70.         while(tnode = lnode->pointers[i])
  71.         {
  72.             if((probe = COMPARE(tnode->korl.key, searchkey))
  73.                 < 0)
  74.             {
  75.                 lnode = tnode;
  76.             }
  77.             else if(probe == NIL)   /* already present */
  78.                 return(tnode);
  79.             else
  80.                 break;  /* break from while loop */
  81.         }
  82.         tempptrs[i] = lnode;
  83.     }
  84.     /* key not yet present in list -- insert it */
  85.     newlevel = randomlevel();
  86.     if(newlevel > searchlist->korl.level)
  87.     {
  88.         for(i = searchlist->korl.level; i < newlevel; ++i)
  89.         {
  90.             tempptrs[i] = searchlist;
  91.         }
  92.         searchlist->korl.level = newlevel;
  93.     }
  94.     lnode = newnode(newlevel, searchkey);
  95.     for(i = 0; i < newlevel; ++i)
  96.     {
  97.         lnode->pointers[i] = tempptrs[i]->pointers[i];
  98.         tempptrs[i]->pointers[i] = lnode;
  99.     }
  100.     return(lnode);
  101. }
  102.  
  103. int delete(searchlist, searchkey)
  104. NODE *searchlist;
  105. KEYTYPE searchkey;
  106. {
  107.     NODE *lnode, *tnode;
  108.     int i;
  109.     NODE *tempptrs[MAXLEVEL];
  110.  
  111.     lnode = searchlist;
  112.     for(i = lnode->korl.level; --i >= 0; )
  113.     {
  114.         while((tnode = lnode->pointers[i])
  115.             && (COMPARE(tnode->korl.key, searchkey) < 0))
  116.         {
  117.             lnode = tnode;
  118.         }
  119.         tempptrs[i] = lnode;
  120.     }
  121.     tnode = lnode->pointers[0];
  122.     if(tnode && (COMPARE(tnode->korl.key, searchkey) == 0))
  123.     {
  124.         lnode = searchlist;
  125.         for(i = 0; i < lnode->korl.level; ++i)
  126.         {
  127.             if(tempptrs[i]->pointers[i] != tnode)
  128.                 break;
  129.             tempptrs[i]->pointers[i] = tnode->pointers[i];
  130.         }
  131.         free(tnode);
  132.         while((i = lnode->korl.level) > 1
  133.             && lnode->pointers[i] == NIL)
  134.         {
  135.             lnode->korl.level = --i;
  136.         }
  137.         return(TRUE);
  138.     }
  139.     else
  140.         return(FALSE);
  141. }
  142.  
  143. NODE *newnode(nlevel, nkey)
  144. int nlevel;
  145. KEYTYPE nkey;
  146. {
  147. #ifdef SLTEST
  148.     extern jmp_buf errbuf;
  149.     extern int *emptr;
  150.     extern int nnodes;
  151.     extern int levels[];
  152. #endif
  153.     NODE *temp;
  154.  
  155.     temp = (NODE *)malloc(sizeof(NODE) +
  156.                     sizeof(NODE *) * (nlevel - 1));
  157. #ifdef SLTEST
  158.     if(temp == NIL)
  159.         longjmp(errbuf, NOMEM); /* best we can do */
  160.     emptr[nnodes] = nkey;   /* record keys as entered */
  161.     nnodes += 1;            /* track number allocated */
  162.     levels[nlevel - 1] += 1;    /* track distribution */
  163. #endif
  164.     temp->korl.key = nkey;  /* NOTE!!! no error checking */
  165.     return(temp);
  166. }
  167.  
  168. int randomlevel();
  169. {
  170.     int slrandom();
  171.     int newlevel;
  172.  
  173. /*
  174.  *  NMAX/DMAX constitute a ratio n/d, such that (d-n)/d
  175.  *  of all nodes will have only 1 pointer and n/d of all
  176.  *  nodes with pointers at any level N will also have
  177.  *  pointers at level N+1
  178.  */
  179.  
  180.     newlevel = 1;
  181.     while(slrandom(DMAX) < NMAX)
  182.         newlevel += 1;
  183.     if(newlevel > DMAX)
  184.         return(DMAX);
  185.     else
  186.         return(newlevel);
  187. }
  188.  
  189.